/*import java.text.DecimalFormat;
import java.util.Scanner;

//顺序
//P5707
public class Luogu {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        double s = scan.nextInt();
        int v = scan.nextInt();
        int t = (int)Math.ceil(s/v) + 10;
        int h = 0, m = 0;
        if(t <= 480) {
            h = (int)((480-t)/60);
            m = (480-t)-(60*h);
        } else if(t > 480) {
            h = (int)((1440-(t-480))/60);
            m = 1440-(t-480)-(60*h);
        }
        DecimalFormat df = new DecimalFormat("00");
        String resh = df.format(h);
        String resm = df.format(m);
        System.out.println(resh+":"+resm);
    }
}*/


/*
import java.util.Scanner;

//顺序
//B2029
public class Luogu {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int h = scan.nextInt();
        int r = scan.nextInt();
        double v = r*r*3.14*h;
        int n = (int)Math.ceil(20*1000/v);
        System.out.println(n);
    }
}*/


/*
import java.util.Scanner;

//P1425
public class Luogu {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();
        int c = scan.nextInt();
        int d = scan.nextInt();
        System.out.println((c-a-1)+" "+(60-b+d));
    }
}*/


/*
import java.util.Scanner;

//P3954
public class Luogu {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();
        int c = scan.nextInt();
        int res = (int)(a*0.2+b*0.3+c*0.5);
        System.out.println(res);
    }
}*/


//P5709
/*
import java.util.Scanner;

public class Luogu {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int m = scan.nextInt();
        double t = scan.nextInt();
        double s = scan.nextInt();
        if(t != 0) {
            m = m - (int)Math.ceil(s/t);
            if(m < 0) {
                m = 0;
            }
        } else if(t == 0) {
            m = 0;
        }
        System.out.println(m);
    }
}*/



//P5710

/*
import java.util.Scanner;

public class Luogu {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int a = 0, u = 0, b = 0, s = 0;
        if(n%2 == 0 && n>4 && n<=12) {
            a = 1;
            u = 1;
        } else if(n%2 == 0 || (n>4 && n <= 12)) {
            u = 1;
            b = 1;
        } else {
            s = 1;
        }
        System.out.println(a+" "+u+" "+b+" "+s);
    }
}*/



//P5711

/*
import java.util.Scanner;

public class Luogu {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int year = scan.nextInt();
        int n = 0;
        if((year % 4 == 0 && year % 100 != 0) || (year % 100 == 0 && year % 400 == 0)) {
            n = 1;
        }
        System.out.println(n);
    }
}*/



//P5712

/*
import java.util.Scanner;

public class Luogu {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int x = scan.nextInt();
        if(x == 0 || x == 1) {
            System.out.println("Today, I ate "+x+" apple.");
        } else {
            System.out.println("Today, I ate "+x+" apples.");
        }
    }
}*/



//P5713

/*
import java.util.Scanner;

public class Luogu {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int Local = n*5;
        int Luogu = n*3+11;
        if(Local < Luogu) {
            System.out.println("Local");
        } else if(Local > Luogu) {
            System.out.println("Luogu");
        }
    }
}*/



//P5714

/*
import java.math.BigDecimal;
import java.math.MathContext;
import java.util.Scanner;

public class Luogu {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        double m = scan.nextDouble();
        double h = scan.nextDouble();
        double BMI = m/(h*h);
        //设置保留6位有效数字
        BigDecimal bd = new BigDecimal(String.valueOf(BMI));
        BigDecimal divisior = BigDecimal.ONE;
        MathContext mc = new MathContext(6);

        if(BMI < 18.5) {
            System.out.println("Underweight");
        } else if(BMI >= 18.5 && BMI < 24) {
            System.out.println("Normal");
        } else if(BMI >= 24) {
            System.out.println(bd.divide(divisior, mc));
            System.out.println("Overweight");
        }
    }
}*/



//P5717

/*mport java.util.Arrays;
import java.util.Scanner;

public class Luogu {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int[] array = new int[3];
        for(int i = 0; i < 3; i++) {
            array[i] = scan.nextInt();
        }
        Arrays.sort(array);
        for(int i = 0; i < 2; i++) {
            System.out.print(array[i]+" ");
        }
        System.out.println(array[2]);
    }
}*/



//P5716

/*
import java.util.Scanner;

public class Luogu {
    public static boolean judge(int y) {
        if((y % 4 == 0 && y % 100 != 0) || (y % 100 == 0 && y % 400 == 0)) {
            return true;
        }
        return false;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int year = scan.nextInt();
        int m = scan.nextInt();
        switch(m) {
            case 1:
            case 3:
            case 5:
            case 7:
            case 8:
            case 10:
            case 12:
                System.out.println(31);
                break;
            case 4:
            case 6:
            case 9:
            case 11:
                System.out.println(30);
                break;
            default:
                if(judge(year) == true) {
                    System.out.println(29);
                    break;
                } else {
                    System.out.println(28);
                    break;
                }
        }
    }
}*/



//P1085

/*
import java.util.Scanner;

public class Luogu {
    public static void main(String[] args) {
        int[][] arr = new int[7][2];
        int i = 0, j = 0, t = 0;
        Scanner scan = new Scanner(System.in);
        for(i = 0; i < 7; i++) {
            for(j = 0; j < 2; j++) {
                arr[i][j] = scan.nextInt();
            }
        }
        int max = arr[0][0] + arr[0][1], res = 0;
        for(i = 0; i < 7; i++) {
            t = arr[i][0] + arr[i][1];
            if(t > max) {
                max = t;
                res = i;
            }
        }
        if(max > 8) {
            System.out.println(res+1);
        } else {
            System.out.println(0);
        }
    }
}*/



//P1909

/*
import java.util.Scanner;

public class Luogu {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        double n = scan.nextDouble();
        int[][] p = new int[3][2];
        for(int i = 0; i < 3; i++) {
            for (int j = 0; j < 2; j++) {
                p[i][j] = scan.nextInt();
            }
        }
        int num = (int)Math.ceil(n/p[0][0]);
        int money = num*p[0][1];
            for(int i = 1; i < 3; i++) {
                int rnum = (int)Math.ceil(n/p[i][0]);
                int rmoney = rnum*p[i][1];
                if(rmoney < money) {
                    money = rmoney;
            }
        }
        System.out.println(money);
    }
}*/



//P5717

/*
import java.util.Arrays;
import java.util.Scanner;

public class Luogu {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int[] array = new int[3];
        for(int i = 0; i < 3; i++) {
            array[i] = scan.nextInt();
        }
        Arrays.sort(array);
        if(array[0] + array[1] < array[2]) {
            System.out.println("Not triangle");
        } if(Math.pow(array[0], 2)+Math.pow(array[1], 2)==Math.pow(array[2], 2)) {
            System.out.println("Right triangle");
        } if(Math.pow(array[0], 2)+Math.pow(array[1], 2) > Math.pow(array[2], 2)) {
            System.out.println("Acute triangle");
        } if(Math.pow(array[0], 2)+Math.pow(array[1], 2) < Math.pow(array[2], 2)) {
            System.out.println("Obtuse triangle");
        } if(array[0] == array[1] || array[1] == array[2] || array[0] == array[2]) {
            System.out.println("Isosceles triangle");
        } if(array[0] == array[1] && array[1] == array[2]) {
            System.out.println("Equilateral triangle");
        }
    }
}*/



//P1422

/*
import java.text.DecimalFormat;
import java.util.Scanner;

public class Luogu {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int e = scan.nextInt();
        double m = 0;
        if(e <= 150) {
            m = e * 0.4463;
        } else if(e > 150 && e <= 400) {
            m = 150*0.4463+(e-150)*0.4663;
        } else if(e > 400) {
            m = 150*0.4463+250*0.4663+(e-400)*0.5663;
        }
        DecimalFormat df = new DecimalFormat("0.0");
        String res = df.format(m);
        System.out.println(res);
    }
}*/



//P1424


/*
import java.util.Scanner;

public class Luogu {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int x = scan.nextInt();
        int n = scan.nextInt();
        int sum = 0;
        for(int i = 0; i < n; i++) {
            if (x != 6 && x != 7) {
                sum += 250;
            }
            if (x == 7) {
                x = 1;
            } else {
                x++;
            }
        }
        System.out.println(sum);
    }
}*/



//P1888


/*
import java.util.Arrays;
import java.util.Scanner;

public class Luogu {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int[] arr = new int[3];
        for(int i = 0; i < 3; i++) {
            arr[i] = scan.nextInt();
        }
        Arrays.sort(arr);
        int a = arr[0];
        int b  =arr[2];
        int c = a % b;
        while(c != 0) {
            a = b;
            b = c;
            c = a % b;
        }
        System.out.println(arr[0]/b+"/"+arr[2]/b);
    }
}*/


/*
import java.util.Arrays;
import java.util.Scanner;

public class Luogu {
    public static void main(String[] args) {
        int[] arr = new int[10];
        Scanner scan = new Scanner(System.in);
        for(int i = 0; i < 10; i++) {
            arr[i] = scan.nextInt();
        }
        int s = scan.nextInt();
        Arrays.sort(arr);
        int n = 0;
        for(int i = 0; i < 10; i++) {
            if(arr[i] <= s+30) {
                n++;
            }
        }
        System.out.println(n);
    }
}*/



//P4414


/*
import java.util.Arrays;
import java.util.Scanner;

public class Luogu {
    public static void main(String[] args) {
        int[] arr = new int[3];
        Scanner scan = new Scanner(System.in);
        for(int i = 0; i < 3; i++) {
            arr[i] = scan.nextInt();
        }
        String ch = scan.next();
        char[] c = new char[3];
        for(int i = 0; i < ch.length(); i++) {
            c[i] = ch.charAt(i);
        }
        Arrays.sort(arr);
        for(int i = 0; i < 3; i++) {
            if(c[i] == 'A') {
                System.out.print(arr[0]+" ");
            } else if(c[i] == 'B') {
                System.out.print(arr[1]+" ");
            } else if(c[i]== 'C') {
                System.out.print(arr[2]+" ");
            }
        }
    }
}*/



//P1055

/*
import java.util.Scanner;

public class Luogu {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String num = scan.next();
        String n = "0123456789X";
        int sum = 0, count = 1;
        char[] ch = num.toCharArray();
        char[] check = n.toCharArray();
        for(int i = 0; i <= 10; i++) {
            int t = ch[i] - '0';
            if(t >= 0 ) {
                sum += t*count;
                count++;
            }
        }
        sum %= 11;
        if(check[sum] == ch[12]) {
            System.out.println("Right");
        } else {
            ch[12] = check[sum];
            System.out.println(new String(ch));
        }
        }
    }*/



//P5718

/*
import java.util.Arrays;
import java.util.Scanner;

public class Luogu {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] num = new int[n];
        for(int i = 0; i < n; i++) {
            num[i] = scan.nextInt();
        }
        Arrays.sort(num);
        System.out.println(num[0]);
    }
}*/



//P5719


/*
import java.text.DecimalFormat;
import java.util.Scanner;

public class Luogu {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int k = scan.nextInt();
        int count1 = 0, count2 = 0;
        double sum1 = 0, sum2 = 0;
        for(int i = 1; i <= n; i++) {
            if(i % k == 0) {
                sum1 += i;
                count1++;
            } else {
                sum2 += i;
                count2++;
            }
        }

        DecimalFormat df = new DecimalFormat("0.0");
        String res = df.format(sum1/count1);
        String res2 = df.format(sum2/count2);
        System.out.println(res+" "+res2);
    }
}*/




//P5720

/*
import java.util.Scanner;

public class Luogu {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int count = 0;
        while(a >= 1) {
            a /= 2;
            count++;
        }
        System.out.println(count);
    }
}*/




//P5721


/*
import java.text.DecimalFormat;
import java.util.Scanner;

public class Luogu {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int count = 1;
        DecimalFormat df = new DecimalFormat("00");
        for(int i = n; i > 0; i--) {
            for(int j = 1; j <= i; j++) {
                String res = df.format(count);
                System.out.print(res);
                count++;
            }
            System.out.print("\n");
        }
    }
}*/




//P1009

/*
import java.math.BigInteger;
import java.util.Scanner;

public class Luogu {
    public static BigInteger jc(int n) {
        BigInteger num = new BigInteger("1");
        for(int i = 2; i <= n; i++) {
            num = num.multiply(new BigInteger(Integer.toString(i)));
        }
        return num;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        BigInteger sum = new BigInteger("0");
        for(int i = 1; i <= n; i++) {
            sum = sum.add(jc(i));
        }
        System.out.println(sum);
    }
}*/



//P1980

/*
import java.util.Scanner;

public class Luogu {
    public static int func(int n, int x) {
        int count = 0;
        while(n > 0) {
            if(n % 10 == x) {
                count++;
            }
            n /= 10;
        }
        return count;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int x = scan.nextInt();
        int res = 0;
        for(int i = 1; i <= n; i++) {
            res += func(i, x);
        }
        System.out.println(res);
    }
}*/



//01背包
/*
import java.util.Scanner;

public class Luogu {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int m = scan.nextInt();
        int n = scan.nextInt();
        int[] w = new int[m];
        int[] v = new int[m];
        for(int i = 0; i < m; i++) {
            w[i] = scan.nextInt();
            v[i] = scan.nextInt();
        }

        int[][] dp = new int[m+1][n+1];
        for(int i = w[0]; i <= n; i++) {
            dp[0][i] = v[0];
        }
        for(int i = 1; i < m; i++) {
            for(int j = 1; j <= n; j++) {
                if(j - w[i] >= 0)
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
                else
                    dp[i][j] = dp[i-1][j];
            }
        }
        System.out.println(dp[m-1][n]);
    }
}*/




//01背包滚动数组

/*
import java.util.Scanner;

public class Luogu {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int m = scan.nextInt();
        int n = scan.nextInt();
        int[] w = new int[m];
        int[] v = new int[m];
        for(int i = 0; i < m; i++) {
            w[i] = scan.nextInt();
            v[i] = scan.nextInt();
        }
        int[] dp = new int[n+1];

        for(int i = 0; i < m; i++) {
            for(int j = n; j >= w[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j-w[i]]+v[i]);
            }
        }
        System.out.println(dp[n]);
    }
}
*/



//完全背包问题
/*import java.util.Scanner;

public class Luogu {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int m = scan.nextInt();
        int n = scan.nextInt();
        int[] w = new int[m];
        int[] v = new int[m];
        for(int i = 0; i < m; i++) {
            w[i] = scan.nextInt();
            v[i] = scan.nextInt();
        }
        int[] dp = new int[n+1];

        for(int i = 0; i < m; i++) {
            for(int j = w[i]; j <= n; j++) {
                dp[j] = Math.max(dp[j], dp[j-w[i]]+v[i]);
            }
        }
        System.out.println(dp[n]);
    }
}*/


//最大路径和
/*
import java.util.Scanner;

public class Luogu {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int m = scan.nextInt();
        int n = scan.nextInt();
        int[][] way = new int[m][n];
        for(int i = 0; i < m; i++) {
            for( int j = 0; j < n; j++) {
                way[i][j] = scan.nextInt();
            }
        }

        int[][] dp = new int[m+1][n+1];

        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + way[i-1][j-1];
            }
        }
        System.out.println(dp[m][n]);
    }
}*/
